package org.prime;

import java.math.BigInteger;

public class LongInteger implements Comparable {
                        protected int [] value;
                protected int size;
                LongInteger(){}
/******************************TESTED*********************************************************************************************************************/
//sets the size of LI (LongInteger)            
                LongInteger(int s){
                        this.size = s;
                        this.value=new int [this.size];
                }
/*****************************TESTED**********************************************************************************************************************/             
//constructor arg is table              
                public LongInteger(int[] tab){
                                this.size = tab.length;
                                this.value=new int [this.size];
                                this.set(tab);
                }
/*******************************************TESTED********************************************************************************************************/             
//normalize numbers in every bit to become between 0 and 9              
                public void normalization (){
                int ile,mod;
                int tab [] ;
                
                for (int i=this.size-1;i>=0;i--)
                {
                        ile = 0;
                        mod = 0;
                        
                        if (this.value[i]>9&&i>0) 
                                {
                                        ile=this.value[i]/10;
                                        mod=this.value[i]%10;
                                        this.value[i] = mod;
                                        this.value[i-1]+=ile;
                                }
                        
                        while (this.value[i]<0&&i>0) 
                        {
                                this.value[i] +=10 ;
                                this.value[i-1]-=1;
                        }
                
                        while (this.value[i]<0&&i==0) 
                        {
                                this.value[i] +=1 ;
                                this.value[i+1]-=10;
                        }
                        
                         if (this.value[i]>9&&i==0)
                                        {
                                        tab = new int [this.size+1];
                                        ile=this.value[i]/10;
                                        mod=this.value[i]%10;
                                        this.size++;
                                        tab[0]=ile;
                                        tab[1]=mod;
                                        for (int k=2;k<this.size;k++)
                                                {
                                                tab[k]=this.value[k-1];
                                                }
                                                
                                        this.value=new int [this.size];
                                                
                                                for (int k=0;k<this.size;k++)
                                                {
                                                        this.value[k]=tab[k];
                                                }}
                        else     if (this.value[i]==0&&i==0)
                         {
                                 LongInteger temp = new LongInteger();
                                 temp.size=this.size-1;
                                 temp.value=new int [temp.size];
                                 for (int j=0;j<temp.size;j++)
                                         temp.value[j]=this.value[j+1];
                                 this.set(temp);
                        }}}              
/**********************************TESTED*****************************************************************************************************************/            
//sets LI basing on tab values
                public void set(int[] tab)
                {
                    this.size=tab.length;       
                
                this.value=new int [this.size];
                        
                        for (int i=0;i<tab.length;i++)
                                {
                                this.value[i]=tab[i];
                                }
                        this.normalization();
                }
/**********************************TESTED*****************************************************************************************************************/            
//makes this to be a copy of x          
                public void set(LongInteger x)
                {
                    this.size=x.size;   
                    this.value=new int [this.size];
                    for (int i=0;i<this.size;i++)
                  this.value[i]=x.value[i];
                    this.normalization();
                } 
                
/**********************************TESTED*****************************************************************************************************************/
//converts LI to string
                public String toString (){
                        String wynik="";
                        for (int i=0;i<this.size;i++)
                                wynik=wynik+this.value[i];
                        return wynik;
                }
/*****************************TESTED**********************************************************************************************************************/
// sets LI to new int value
                public void set(int value)
                {
                        String string="";
                        string+=value;
                        this.size=string.length();
                        this.value=new int[this.size];          
                        for (int i=0;i<this.size;i++)
                {
                this.value[i]=value/(int)Math.pow(10,this.size-1-i);
                value=value%(int)Math.pow(10,this.size-1-i);
                }}
/**********************************TESTED*****************************************************************************************************************/        
                //returns LI which is sum of this LI and x LI
                public LongInteger add2 (LongInteger x)
                        {
                        LongInteger wynik = new LongInteger();
                        LongInteger temp = new LongInteger();
                        int srodek=0,koniec=0;
                        if (this.size>=x.size)
                        {
                                koniec=this.size;
                                srodek=x.size;
                                temp.size=koniec;
                                temp.value=new int [temp.size];
                                for (int i=koniec-1;i>=0;i--)
                                {
                                        if (srodek>0)
                                                { 
                                                temp.value[i]=x.value[srodek-1];
                                                srodek--;
                                                }}
                                wynik.size=koniec;
                                wynik.value=new int [koniec];
                                for (int i=koniec-1;i>=0;i--)
                                        {
                                    wynik.value[i]=(temp.value[i] + this.value[i]);
                                        }}      
                            
                        else 
                                {
                                koniec=x.size;
                                srodek=this.size;
                                temp.size=koniec;
                                temp.value=new int [temp.size];
                                for (int i=koniec-1;i>=0;i--)
                                {
                                        if (srodek>0)
                                                { 
                                                temp.value[i]=this.value[srodek-1];
                                                srodek--;
                                                }}
                                
                                        wynik.size=koniec;
                                        wynik.value=new int [koniec];
                                                for (int i=koniec-1;i>=0;i--)
                                                        {
                                                        wynik.value[i]= (temp.value[i] + x.value[i]);
                                                        }}
                                wynik.normalization();                  
                        return wynik;   
                        }
/**********************************TESTED*****************************************************************************************************************/        
//this minus x
                public LongInteger minus (LongInteger x)
                        {
                        LongInteger wynik = new LongInteger();
                        LongInteger temp = new LongInteger();
                        int srodek=0,koniec=0;
                        if (this.size>=x.size)
                        {
                                koniec=this.size;
                                srodek=x.size;
                                temp.size=koniec;
                                temp.value=new int [temp.size];
                                for (int i=koniec-1;i>=0;i--)
                                {
                                        if (srodek>0)
                                                { 
                                                temp.value[i]=x.value[srodek-1];
                                                srodek--;
                                                }}
                                wynik.size=koniec;
                                wynik.value=new int [koniec];
                                for (int i=koniec-1;i>=0;i--)
                                        {
                                    wynik.value[i]=(this.value[i] - temp.value[i]);
                                        }}      
                            
                        else 
                                {
                                koniec=x.size;
                                srodek=this.size;
                                temp.size=koniec;
                                temp.value=new int [temp.size];
                                for (int i=koniec-1;i>=0;i--)
                                {
                                        if (srodek>0)
                                                { 
                                                temp.value[i]=this.value[srodek-1];
                                                srodek--;
                                                }}
                                
                                        wynik.size=koniec;
                                        wynik.value=new int [koniec];
                                                for (int i=koniec-1;i>=0;i--)
                                                        {
                                                        wynik.value[i]= (temp.value[i] - x.value[i]);
                                                        }}
                                wynik.normalization();                  
                        return wynik;   
                        }

                /***************************************TESTED************************************************************************************************************/             
              //increments this LI by x LI
                public void add (LongInteger x)
                        {
                        //temp = LI o rozmiarze wiekszego LI, ale wartosci mniejszego
                        LongInteger temp = new LongInteger();
                        int srodek=0,koniec=0;
                        if (x!=null)
                        if (this.size>=x.size)
                        {
                                koniec=this.size;
                                srodek=x.size;
                                temp.size=koniec;
                                temp.value=new int [temp.size];
                                for (int i=koniec-1;i>=0;i--)
                                {
                                        if (srodek>0)
                                                { 
                                                temp.value[i]=x.value[srodek-1];
                                                srodek--;
                                                }}
                                
                                for (int i=koniec-1;i>=0;i--)
                                        {
                                   this.value[i]=(this.value[i]+temp.value[i]);

                                        this.normalization();
                                        }}      
                            
                        else 
                                {
                                koniec=x.size;
                                srodek=this.size;
                                temp.size=koniec;
                                temp.value=new int [temp.size];
                                for (int i=koniec-1;i>=0;i--)
                                {
                                        if (srodek>0)
                                                { 
                                                temp.value[i]=this.value[srodek-1];
                                                srodek--;
                                                }}
                                LongInteger temp2 = new LongInteger(x.size);
                                //this.value=new int[this.size];
                                
                                for (int i=koniec-1;i>=0;i--)
                                        {
                                   temp2.value[i]=(temp.value[i]+x.value[i]);

                                        this.normalization();
                                        }
                                this.set(temp2);
                                }}
                /***************************************TESTED************************************************************************************************************/             
                      //decrements this LI by x LI
                        public void decrement (LongInteger x)
                                {
                                //temp = LI o rozmiarze wiekszego LI, ale wartosci mniejszego
                                LongInteger temp = new LongInteger();
                                int srodek=0,koniec=0;
                                if (this.size>=x.size)
                                {
                                        koniec=this.size;
                                        srodek=x.size;
                                        temp.size=koniec;
                                        temp.value=new int [temp.size];
                                        for (int i=koniec-1;i>=0;i--)
                                        {
                                                if (srodek>0)
                                                        { 
                                                        temp.value[i]=x.value[srodek-1];
                                                        srodek--;
                                                        }}
                                        
                                        for (int i=koniec-1;i>=0;i--)
                                                {
                                           this.value[i]=(this.value[i]-temp.value[i]);
                                                }}      
                                    
                                else 
                                        {
                                        koniec=x.size;
                                        srodek=this.size;
                                        temp.size=koniec;
                                        temp.value=new int [temp.size];
                                        for (int i=koniec-1;i>=0;i--)
                                        {
                                                if (srodek>0)
                                                        { 
                                                        temp.value[i]=this.value[srodek-1];
                                                        srodek--;
                                                        }}
                                        
                                                
                                                        for (int i=koniec-1;i>=0;i--)
                                                                {
                                                                this.value[i]= (x.value[i]-temp.value[i]);
                                                                }}
                                        this.normalization();                   
                                }
/*****************************************TESTED**********************************************************************************************************/             
                public boolean greater (LongInteger x){
                         if (this.size==x.size)
                                {
                                        for (int i=0;i<this.size;i++)
                                                if (this.value[i]<x.value[i])
                                                        return false;
                                                else if (this.value[i]>x.value[i])
                                                        return true;
                                                return false;
                                }
                                 if (this.size>x.size)
                                {
                                        for (int i=0;i<Math.abs(this.size-x.size);i++)
                                                {
                                                if (this.value[i]>0)
                                                return true;
                                                }
                                for (int i=0;i<x.size;i++)
                                        {
                                        if (this.value[i+Math.abs(this.size-x.size)]>x.value[i])
                                                return true;
                                        if (this.value[i+Math.abs(this.size-x.size)]<x.value[i])
                                                return false;
                                        }       
                               return false; 
                                }
                                 if (this.size<x.size)
                                {
                                        for (int i=0;i<Math.abs(this.size-x.size);i++)
                                        {
                                        if (x.value[i]>0)
                                                return false;
                                        }
                                        for (int i=0;i<this.size;i++)
                                        {
                                        if (this.value[i]>x.value[i+Math.abs(this.size-x.size)])
                                                return true;
                                        if (this.value[i]<x.value[i+Math.abs(this.size-x.size)])
                                                return false;
                                        }       
                               return false;
                                }
                   return false;    
                }
/******************************************TESTED*********************************************************************************************************/
                public boolean equals (LongInteger x){
                         if (this.size==x.size)
                                {
                                        for (int i=0;i<this.size;i++)
                                                if (this.value[i]!=x.value[i])
                                                        return false;
                                                
                                        return true;
                                }
                                 if (this.size>x.size)
                                {
                                        for (int i=0;i<Math.abs(this.size-x.size);i++)
                                                {
                                                if (this.value[i]>0)
                                                return false;
                                                }
                                        for (int i=0;i<x.size;i++)
                                                {
                                                if (this.value[i+Math.abs(this.size-x.size)]!=x.value[i])
                                                return false;
                                        
                                                }       
                               return true; 
                                
                                
                                }
                                 if (this.size<x.size)
                                {
                                         for (int i=0;i<Math.abs(this.size-x.size);i++)
                                                {
                                                if (x.value[i]>0)
                                                return false;
                                                }
                                         
                                        for (int i=0;i<this.size;i++)
                                                {
                                                if (this.value[i]!=x.value[i+Math.abs(this.size-x.size)])
                                                return false;        
                                                }
                                        return true;
                                  }
                        return false;         
                }
/*******************************************TESTED********************************************************************************************************/
                    public boolean lesser (LongInteger x){

                         if (this.size==x.size)
                                {
                                        for (int i=0;i<this.size;i++)
                                                if (this.value[i]<x.value[i])
                                                        return true;
                                                else if (this.value[i]>x.value[i])
                                                        return false;
                                                return false;
                                }
                                 if (this.size>x.size)
                                {
                                        for (int i=0;i<Math.abs(this.size-x.size);i++)
                                                {
                                                if (this.value[i]>0)
                                                return false;
                                                }
                                for (int i=0;i<x.size;i++)
                                        {
                                        if (this.value[i+Math.abs(this.size-x.size)]>x.value[i])
                                                return false;
                                        if (this.value[i+Math.abs(this.size-x.size)]<x.value[i])
                                                return true;
                                        }       
                               return false; 
                                }
                                 if (this.size<x.size)
                                {
                                        for (int i=0;i<Math.abs(this.size-x.size);i++)
                                        {
                                        if (x.value[i]>0)
                                                return true;
                                        }
                                        for (int i=0;i<this.size;i++)
                                        {
                                        if (this.value[i+Math.abs(this.size-x.size)]>x.value[i])
                                                return false;
                                        if (this.value[i+Math.abs(this.size-x.size)]<x.value[i])
                                                return true;
                                        }       
                               return false;
                                }
                   return false;    
                                }
/**********************************TESTED*****************************************************************************************************************/             
public boolean greaterOrEqual(LongInteger x) {
    if (this.size == x.size) {
            for (int i = 0; i < this.size; i++)
                    if (this.value[i] < x.value[i]) {
                            return false;
                    }
            return true;
    }
      if (this.size>x.size)
     {
        for (int i=0;i<Math.abs(this.size-x.size);i++)
                {
                if (this.value[i]>0)
                return true;
                }
        for (int i=0;i<x.size;i++)
                {
                if (this.value[i+Math.abs(this.size-x.size)]<x.value[i])
                        return false;
                }       
                return true; 
     }
      if (this.size<x.size)
     {
        for (int i=0;i<Math.abs(this.size-x.size);i++)
        {
        if (x.value[i]>0)
                return false;
        }
        for (int i=0;i<this.size;i++)
                {
                if (this.value[i]<x.value[i+Math.abs(this.size-x.size)])
                        return false;
                }       
    return true;
     }
return false;    

}
/****************************TESTED***********************************************************************************************************************/             
public boolean lesserOrEqual(LongInteger x) {
        if (this.size == x.size) {
        for (int i = 0; i < this.size; i++)
                if (this.value[i] > x.value[i]) {
                        return false;
                }
        return true;
}
  if (this.size>x.size)
 {
        for (int i=0;i<Math.abs(this.size-x.size);i++)
                {
                if (this.value[i]>0)
                        return false;
                }
        for (int i=0;i<x.size;i++)
                {
                if (this.value[i+Math.abs(this.size-x.size)]>x.value[i])
                        return false;
                }       
                return true; 
 }
  if (this.size<x.size)
 {
        for (int i=0;i<Math.abs(this.size-x.size);i++)
        {
        if (x.value[i]>0)
                return true;
        }
        for (int i=0;i<this.size;i++)
                {
                if (this.value[i]>x.value[i+Math.abs(this.size-x.size)])
                        return false;
                }       
return true;
 }
return false;    
    
}
/******************************************************TESTED*********************************************************************************************/             
// this * x
public void multiply (LongInteger x)
                {
                        LongInteger temp = new LongInteger();
                        int srodek=0,koniec=0;
                        if (this.size>=x.size)
                        {
                                koniec=this.size;
                                srodek=x.size;                                         
                                temp.size=koniec;                                                                                                                       
                                temp.value=new int[temp.size];                          
                                for (int i=koniec-1;i>=0;i--)
                                {
                                        if (srodek>0)
                                                { 
                                                temp.value[i]=x.value[srodek-1];
                                                srodek--;
                                                }}
                                int schowek,mnoznik;
                                for (int i=koniec-1;i>=0;i--)
                                {
                                        mnoznik=0;
                                        schowek=0;
                                        for (int j=koniec-1;j>=0;j--)
                                        {
                                                schowek=schowek + (int) (Math.pow(10, mnoznik)*this.value[i]*temp.value[j]);
                                                mnoznik++;
                                        }
                                        this.value[i]=schowek;
                                }
                                this.normalization();
                            }
                            else 
                                {
                                koniec=x.size;
                                srodek=this.size;
                                temp.size=koniec;
                                temp.value=new int [temp.size];
                                for (int i=koniec-1;i>=0;i--)
                                {
                                        if (srodek>0)
                                                { 
                                                temp.value[i]=this.value[srodek-1];
                                                srodek--;
                                                }}
                                this.size=koniec;
                                this.value=new int [this.size];
                                
                        int schowek,mnoznik;
                        for (int i=koniec-1;i>=0;i--)
                        {
                                mnoznik=0;
                                schowek=0;
                                for (int j=koniec-1;j>=0;j--)
                                {
                                        schowek=schowek + (int) (Math.pow(10, mnoznik)*x.value[i]*temp.value[j]);
                                        mnoznik++;
                                }
                                this.value[i]=schowek;
                        }
                        this.normalization();
                                }}
/************************************************TESTED***************************************************************************************************/
//returns this * x      
public LongInteger multiply2 (LongInteger x)
                {
        LongInteger temp = new LongInteger();
    int srodek=0,koniec=0;
    if (this.size>=x.size)
    {
        koniec=this.size;
        srodek=x.size;                                          
        temp.size=koniec;                                                                                                                       
        temp.value=new int[temp.size];                          

        LongInteger wynik = new LongInteger(koniec);

        for (int i=koniec-1;i>=0;i--)
        {
                if (srodek>0)
                        { 
                        temp.value[i]=x.value[srodek-1];
                        srodek--;
                        }}
        int schowek,mnoznik;
        for (int i=koniec-1;i>=0;i--)
        {
                mnoznik=0;
                schowek=0;
                for (int j=koniec-1;j>=0;j--)
                {
                        schowek=schowek + (int) (Math.pow(10, mnoznik)*this.value[i]*temp.value[j]);
                        mnoznik++;
                }
                wynik.value[i]=schowek;
        }
        wynik.normalization();
        return wynik;
    }
    else 
        {
        koniec=x.size;
        srodek=this.size;
        temp.size=koniec;
        temp.value=new int [temp.size];
        LongInteger wynik = new LongInteger(koniec);
        for (int i=koniec-1;i>=0;i--)
        {
                if (srodek>0)
                        { 
                        temp.value[i]=this.value[srodek-1];
                        srodek--;
                        }}
        
    int schowek,mnoznik;
        for (int i=koniec-1;i>=0;i--)
        {
                mnoznik=0;
                schowek=0;
                for (int j=koniec-1;j>=0;j--)
                {
                        schowek=schowek + (int) (Math.pow(10, mnoznik)*x.value[i]*temp.value[j]);
                        mnoznik++;
                }
                wynik.value[i]=schowek;
        }
        wynik.normalization();
                return wynik; 
        }}
/******************TESTED*********************************************************************************************************************************/
//returns this % x              
public LongInteger mod(LongInteger x)

	{
	LongInteger wynik=new LongInteger();    

	if (x.size>=0){
                                        LongInteger jeden=new LongInteger();
                                LongInteger temp=new LongInteger();
                                LongInteger temp2=new LongInteger();
                                LongInteger mnoznik=new LongInteger();
     
                                
                                
                                temp.set(x);
                                jeden.set(1);
                                mnoznik.set(0);
                                
                                while(temp.lesser(this)) 
                                {
                                        temp.set(temp.add2(x));
                                        mnoznik.set(mnoznik.add2(jeden));                                                                                                
                                }       
                                if (temp.equals(this))
                                {
                                        wynik.set(0);
                                        return wynik;
                                }
                                
                        temp2.set(x.multiply2(mnoznik));
                        wynik.set(this.minus(temp2));
                        wynik.normalization();
	}
                        return wynik;                   
	}             
/************************************TESTED***************************************************************************************************************/             
             // returns sqrt(B) rounded up
                public LongInteger sqrt(LongInteger B){                 
                        LongInteger jeden=new LongInteger();
                        jeden.set(1);
                        LongInteger temp=new LongInteger();
                        temp.set(1);
                        
                        while (temp.multiply2(temp).lesser(B))
                        {
                                temp.set(temp.add2(jeden));
                        }
                        return temp;
                        }              
/***********************************TESTED****************************************************************************************************************/             
             // returns sqrt(this) rounded up 
                public LongInteger sqrt(){
                        
                	LongInteger jeden=new LongInteger();
                    
                	jeden.set(1);
//                    this.add2(jeden);
                	LongInteger temp=new LongInteger();
                        temp.set(1);
                        LongInteger mnoz = temp.multiply2(temp);
                        while (this.greater(mnoz))
                        {
                         
                        	temp.set((temp.add2(jeden)));

                        	mnoz.set(temp.multiply2(temp));
                        }
                        if (this.lesser(mnoz.multiply2(mnoz)))
                        	temp.decrement(jeden);
                        return temp;
                    }           
/*********************TESTED***********************************************************************************/
//checks if this is divisible by x              
                public boolean divisibleBy(LongInteger x){
                        LongInteger mod=new LongInteger();
                mod=(this.mod(x));
                LongInteger zero=new LongInteger();
                zero.set(0);
                if (mod.greater(zero))
                        return false;
                else
                        return true;
        }
/***********************************************TESTED*********************************************************/
                public LongInteger divideIt(LongInteger divisor){
                        LongInteger jeden=new LongInteger(1);
                        LongInteger ile=new LongInteger(1);
                        jeden.set(1);
                        ile.set(0);
                        LongInteger suma=new LongInteger();
                        suma.set(divisor);
                        while (suma.lesser(this)||suma.equals(this))
                        {
                                suma.set(suma.add2(divisor));
                                ile.set(ile.add2(jeden));
                        }
                        return ile;
                        }        
/***********************************************TESTED*********************************************************/
                public LongInteger divide(LongInteger divisor){
                        LongInteger jeden=new LongInteger(1);
                        LongInteger ile=new LongInteger(1);
                        jeden.set(1);
                        ile.set(0);
                        LongInteger suma=new LongInteger(divisor.size);
                        suma.set(divisor);
                        while (suma.lesser(this)||suma.equals(this))
                        {
                                suma.set(suma.add2(divisor));
                                ile.set(ile.add2(jeden));
                        }
                        this.set(ile) ;
                        return this;
                        }        
/********************************************************************************************************/
@Override
public int compareTo(Object arg0) {
        // TODO Auto-generated method stub
        return 0;
}
/********************************************************************************************************/
}